package medium

import (
	. "GoLeetcode/common"
	"math"
)

/*
时间复杂度:O(N)
空间复杂度:O(N)

难：如果找到132的结构
解：secondMin维护的是第二大的数,单调栈栈顶维护的是最大的元素，而nums[i]遍历的是最小的元素

*/

func find132pattern(nums []int) bool {
	secondMin := math.MinInt32
	stack := make([]int, 0)
	for i := len(nums) - 1; i >= 0; i-- {
		if nums[i] < secondMin {
			return true
		}
		// 这里为啥secondMin要取最大的secondMin??
		// 因为如果满足len(stack) > 0 && nums[i] > stack[len(stack)-1], 则说明当前肯定存在32的结构，即当前nums[i]可以作为3，栈顶元素作为2
		// 接下来将栈顶元素出栈，将nums[i]放入栈顶，即栈顶维护最大的元素, 而k此时取最大的，其实是为了使在当前nums[i]的左边的数有更大的概率小于secondMin
		// 因为32的结构肯定是存在的，那么在众多32结构中，选择最大的那个2结构，可以最大概率的找到1
		for len(stack) > 0 && nums[i] > stack[len(stack)-1] {
			secondMin = Max(secondMin, stack[len(stack)-1])
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, nums[i])
	}
	return false
}
